package com.zhugang.week08;

/**
 * @program algorithms
 * @description: bage
 * @author: chanzhugang
 * @create: 2022/08/17 18:40
 */
public class Bage2 {

    /**
     * 0-1 背包问题
     *
     * @param nums
     * @param w
     * @return
     */
    private int maxW = Integer.MIN_VALUE;

    public int bage(int[] nums, int w) {
        // 从n个数中选择，最大能装多少，装或者不装
        backtrack(nums, 0, 0, w);
        return maxW;
    }

    /**
     * @param nums 选择列表，装或者不装
     * @param k    阶段
     * @param cw   路径，已经装了多少
     * @param w    限制
     */
    private void backtrack(int[] nums, int k, int cw, int w) {
        if (k == nums.length || cw == w) {
            // 决策完了或者 装满了
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }

        // 不装，下一个决策
        backtrack(nums, k + 1, cw, w);

        // 装
        if (cw + nums[k] <= w) {
            // 没有装满，装，下一个决策
            backtrack(nums, k + 1, cw + nums[k], w);
        }
    }
}
